import collections


class Solution(object):
    def threeSumMulti(self, arr, target):
        mod = 10 ** 9 + 7
        d = collections.Counter(arr)
        k = list(d.keys())
        k.sort()
        m = len(k)
        t = 0
        for i in range(m):
            if d[k[i]] >= 2:
                base = 2 * k[i]
                if target - base in d:
                    if target - base == k[i]:
                        if d[k[i]] >= 3:
                            t = (t + d[k[i]] * (d[k[i]] - 1) * (d[k[i]] - 2) // 6) % mod
                    else:
                        t = (t + (d[k[i]] * (d[k[i]] - 1) // 2) * d[target - base]) % mod
            for j in range(i + 1, m):
                base = k[i] + k[j]
                if target - base in d:
                    if target - base > k[j]:
                        t = (t + d[k[i]] * d[k[j]] * d[target - base]) % mod
        return t


data = Solution()
arr = [1, 1, 2, 2, 3, 3, 4, 4, 5, 5]
target = 8
print(data.threeSumMulti(arr, target))
